# -- coding: utf-8 --


class Solution(object):
    #动态规划
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        m = 0
        dp = [0]*len(s)
        for i in range(1,len(s)):
            if s[i] == ')':
                if s[i-1] == '(':
                    dp[i] = dp[i-2]+2 if i >= 2 else 2
                elif i-dp[i-1]>0 and s[i-dp[i-1]-1] == '(':
                    dp[i] = dp[i-1]+(dp[i - dp[i - 1] - 2]+2 if i-dp[i-1] >= 2 else 2)
                m= max(m,dp[i])
        return m


    #用栈
    def longestValidParentheses1(self, s):
        """
        :type s: str
        :rtype: int
        """
        m = 0
        stack = []
        for i in range(0, len(s)):
            if s[i] == ')' and len(stack) != 0 and s[stack[-1]] == '(':
                stack.pop()
                m = max(m, i-(-1 if len(stack) == 0 else stack[-1]))
            else:
                stack.append(i)
        return m


test = Solution()
print(test.longestValidParentheses1("(()"))